/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package pagrafo.genetico;

import java.util.LinkedList;
import pagrafo.grafo.Grafo;

/**
 *
 * @author Fabricio
 */
public class CrossoverRotas {
    
    private static void getRoute(LinkedList<Integer> rota, int p[], int numRota) {
        
        int count = 0;
        
        for (int i = 0; i < p.length; i++) {
            
            if (p[i] == 0) {
                count++;
            }
            if (count == numRota) {
                rota.add(p[i + 1]);
            }
            if (count == numRota + 1) {
                rota.removeLast();
                break;
            }
        }
        
    }
    
    private static boolean containsRoute(LinkedList<Integer> rota, LinkedList<Integer> f1) {
        
        for (int i = 0; i < rota.size(); i++) {
            if (f1.contains(rota.get(i))) {
                return true;
            }
        }
        
        return false;
    }
    
    private static boolean containsConsumer(int n, LinkedList<Integer> f1) {
        
        if (f1.contains(n)) {
            return true;
        }
        
        return false;
    }
    
    private static void addRoute(LinkedList<Integer> f1, LinkedList<Integer> rota) {
        f1.add(0);
        f1.addAll(rota);
        
    }
    
    private static int[] crossover(int p1[], int p2[], int maxRoutes, int maxConsumers) {
        
        LinkedList<Integer> f1 = new LinkedList();
        LinkedList<Integer> rotaP1 = new LinkedList();
        LinkedList<Integer> rotaP2 = new LinkedList();
        
        int numRotaP1 = 1;
        int numRotaP2 = maxRoutes;
        
        
        boolean p1Acabou = false;
        boolean p2Acabou = false;
        
        while (!p1Acabou || !p2Acabou) {
            
            boolean adicionouRota1 = false;
            
            if (!p1Acabou) {
                
                getRoute(rotaP1, p1, numRotaP1);
                
                while (!adicionouRota1) {
                    
                    
                    if (!containsRoute(rotaP1, f1)) {
                        addRoute(f1, rotaP1);
//                        System.out.println("add rota");
//                        for (int i = 0; i < f1.size(); i++) {
//                            System.out.println(f1.get(i));
//                        }
                        if (countZeros(f1) == maxRoutes) {
                            rotaP1.clear();
                            adicionouRota1 = true;
                            p1Acabou = true;
                            break;
                        }
                        rotaP1.clear();
                        adicionouRota1 = true;
                        
                        numRotaP1++;
                        if (numRotaP1 == maxRoutes) {
//                        if (numRotaP1 == maxRoutes) {
                            p1Acabou = true;
                            
                            break;
                        }
                        
                    } else {
                        rotaP1.clear();
                        numRotaP1++;
                        if (numRotaP1 == maxRoutes) {
//                         if (numRotaP1 == maxRoutes) {
                            p1Acabou = true;
                            
                            break;
                        } else {
                            getRoute(rotaP1, p1, numRotaP1);
                        }
                    }
                }
            }
            
            boolean adicionouRota2 = false;
            
            if (!p2Acabou) {
                
                getRoute(rotaP2, p2, numRotaP2);
                
                while (!adicionouRota2) {
                    
                    
                    if (!containsRoute(rotaP2, f1)) {
                        addRoute(f1, rotaP2);
//                         System.out.println("add rota");
//                        for (int i = 0; i < f1.size(); i++) {
//                            System.out.println(f1.get(i));
//                        }
                        if (countZeros(f1) == maxRoutes) {
                            rotaP2.clear();
                            adicionouRota2 = true;
                            p2Acabou = true;
                            break;
                        }
                        rotaP2.clear();
                        adicionouRota2 = true;
                        
                        numRotaP2--;
                        if (numRotaP2 == 0) {
                            p2Acabou = true;
                            
                            break;
                        }
                        
                    } else {
                        rotaP2.clear();
                        numRotaP2--;
                        if (numRotaP2 == 0) {
                            p2Acabou = true;
                            
                            break;
                        } else {
                            getRoute(rotaP2, p2, numRotaP2);
                        }
                    }
                }
                
            }
        }
        int maxSize = maxConsumers + (maxRoutes);
        f1 = fillChromosome(f1, maxSize, maxRoutes);       
        f1.add(0);

        //Verifica se existe zeros a mais
//        if (countZeros(f1) != maxRoutes + 1) {
//            f1 = retiraZero(f1, maxSize, maxRoutes);
//        }

        int[] c = new int[f1.size()];
        for (int i = 0; i < f1.size(); i++) {
            c[i] = f1.get(i).intValue();
        }
        
        return c;
        
    }
    
    private static LinkedList<Integer> fillChromosome(LinkedList<Integer> f, int numMax, int maxRoutes) {
        
        int n = 1;
        
        int zerosFaltando = maxRoutes - countZeros(f);
        int offset = (numMax - f.size()) / 2;
        
        for (int i = 1; i < zerosFaltando; i++) {
            offset = offset / 2;
        }
        int index = f.size();
        index = index + offset;
        
        while (f.size() < numMax) {
            
            
            if (zerosFaltando > 0 && (f.size() == index + 1)) {
                
                f.set(index, 0);
                index = index + offset;
                zerosFaltando--;
            } else {
                if (!containsConsumer(n, f)) {
                    f.add(n);
                } else {
                    n++;
                }
            }
        }
        
        
        return f;
    }
    
    private static LinkedList<Integer> preencheCromossomo(LinkedList<Integer> f, int numMax, int maxRoutes) {
        
        int n = 0;
        LinkedList<Integer> lista = new LinkedList<Integer>();
        int zerosFaltando = maxRoutes - countZeros(f);
        int tamanho = (numMax - f.size());
        int offset = tamanho - 1 / zerosFaltando;
        int i = 0;
       
        lista.add(0);
       
        while ( i + offset < tamanho) {
            lista.set(i, 0);            
            i = i + offset;            
        }
        
        i = 0;
        while (i < tamanho) {
            if (!containsConsumer(n, lista) && lista.get(i).intValue() != 0) {
                lista.add(n);
            } else {
                n++;
            }
        }
        
        f.addAll(lista);                
        
        return f;
    }
    
    public static int countZeros(LinkedList<Integer> f) {
        int n = 0;
        for (int i = 0; i < f.size(); i++) {
            if (f.get(i) == 0) {
                n++;
            }
        }
        return n;
    }
    
    public static int countZeros(int[] v) {
        int n = 0;
        for (int i = 0; i < v.length; i++) {
            if (v[i] == 0) {
                n++;
            }
        }
        return n;
    }
    
    private static LinkedList<Integer> retiraZero(LinkedList<Integer> f1, int numMax, int maxRoutes) {
        
        for (int i = 0; i < f1.size(); i++) {
            if (f1.get(i) == 0 && i != 0) {
                f1.remove(i);
            }
        }
        f1 = fillChromosome(f1, numMax, maxRoutes);
        return f1;
    }
    
    public static Cromossomo[] executar(Cromossomo paiA, Cromossomo paiB, Grafo g, int k, double capacidade){
        int[] genes;
        Cromossomo[] cromossomos = new Cromossomo[2];
        
        genes = CrossoverRotas.crossover(paiA.v, paiB.v, k, g.getDimensao() - 1);
        if (CrossoverRotas.countZeros(genes) == CrossoverRotas.countZeros(paiA.v)) {
            cromossomos[0] = new Cromossomo(g, k, capacidade, genes);
        }
        genes = CrossoverRotas.crossover(paiB.v, paiA.v, k, g.getDimensao() - 1);
        if (CrossoverRotas.countZeros(genes) == CrossoverRotas.countZeros(paiB.v)) {
            cromossomos[1] = new Cromossomo(g, k, capacidade, genes);
        }   
        return cromossomos;
    }
}
